package 下一个更大元素I;

import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;

/**
 * @author: AirMan
 * @date: 2025/5/22 20:56
 * @description:
 * 给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
 * 请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
 * nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
 * 示例 1:
 * 输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
 * 输出: [-1,3,-1]
 * 解释:
 * 对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
 * 对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
 * 对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
 * 示例 2:
 * 输入: nums1 = [2,4], nums2 = [1,2,3,4].
 * 输出: [3,-1]
 * 解释:
 * 对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
 * 对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出-1 。
 * 提示：
 * 1 <= nums1.length <= nums2.length <= 1000
 * 0 <= nums1[i], nums2[i] <= 10^4
 * nums1和nums2中所有整数 互不相同
 * nums1 中的所有整数同样出现在 nums2 中
 */
public class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 数组中出现的第一个最值问题 ==> 单调栈
        // 找第一个大的元素，那么单调栈从 栈顶到栈底 是递增的

        Deque<Integer> stack = new LinkedList<>();
        int[] result = new int[nums1.length];
        Arrays.fill(result, -1);
        // 检查一个元素是否存在：哈希法
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            map.put(nums1[i], i);
        }

        // 遍历 nums1 中的元素，用当前遍历到的元素和栈顶索引所代表的元素进行比较
        // 如果 nums[i] > stack.peek()，那么就将栈顶索引弹出
        //                  并检查 nums1[index]的值是否出现在 nums2 中，如果出现了，那么该值的结果为：i - index
        //                  如果没出现就不管
        // 如果 nums[i] <= stack.peek()，那么就将当前元素入栈

        stack.push(0);
        for (int i = 1; i < nums2.length; i++) {
            while (nums2[i] > nums2[stack.peek()]) {
                int topIndex = stack.pop();
                Integer resultIndex = map.get(nums2[topIndex]);
                // 利用哈希法检查 nums2 中是否存在该栈顶元素
                if (resultIndex != null) {
                    result[resultIndex] = nums2[i];
                }
                // 继续检查下一个栈顶元素
                if (stack.isEmpty()) {
                    break;
                }
            }
            // 将当前元素的索引入栈
            stack.push(i);
        }
        return result;
    }
}
